#include "BinaryTreeExample.h"

TreeNode* BinaryTreeExample::InvertTree(TreeNode* root) {
    // 遍历二叉树，交换每个节点的子节点
    // Traverse(root);
    // return root;
    return InvertTreeBySubTree(root);
}

void BinaryTreeExample::Traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    // 交换左右子节点
    TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;

    Traverse(root->left);
    Traverse(root->right);
}


TreeNode* BinaryTreeExample::InvertTreeBySubTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }

    // 子问题：把左子树翻转和右子树翻转，然后在给根节点
    TreeNode* left = InvertTreeBySubTree(root->left);
    TreeNode* right = InvertTreeBySubTree(root->right);

    // 交换子树位置
    root->left = right;
    root->right = left;
    return root;
}